﻿#include <iostream>

void Bublesort(int a[], int n)
{
	int i, j, k;

	for (j = 0; j < n; j++)
	{
		for (i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				k = a[i];
				a[i] = a[i + 1];
				a[i + 1] = k;
			}
		}
	}
}

int QuickSortPartition(int *data, int low, int high)
{
	int t = 0;

	t = data[low];

	while (low < high)
	{
		while (low < high && data[high] >= t)
			high--;

		data[low] = data[high];

		while (low < high && data[low] <= t)
			low++;

		data[high] = data[low];
	}

	data[low] = t;

	return low;
}

void QuickSort(int *data, int low, int high)
{
	if (low >= high)
		return;

	int pivotloc = 0;

	pivotloc = QuickSortPartition(data, low, high);

	QuickSort(data, low, pivotloc - 1);

	QuickSort(data, pivotloc + 1, high);
}

void InsertSort(int arr[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = arr[i];
		int j = i;

		while ((j > 0) && (arr[j - 1] > temp))
		{
			arr[j] = arr[j - 1];
			--j;
		}

		arr[j] = temp;
	}
}

void BInsertSort(int data[], int n)
{
	int low, high, mid;
	int temp, i;

	for (i = 1; i < n; i++)
	{
		low = 0;
		temp = data[i];
		high = i - 1;

		while (low <= high)
		{
			mid = (low + high) / 2;

			if (data[mid] > temp)
				high = mid - 1;
			else
				low = mid + 1;
		}

		int j = i;
		while ((j > low) && (data[j - 1] > temp))
		{
			data[j] = data[j - 1];
			--j;
		}

		data[low] = temp;
	}
}

void ShellSort(int *data, int size)
{
	for (int gap = size / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < size; ++i)
		{
			int key = data[i];
			int j = 0;

			for (j = i - gap; j >= 0 && data[j] > key; j -= gap)
			{
				data[j + gap] = data[j];
			}

			data[j + gap] = key;
		}
	}
}

void HeapAjust(int data[], int i, int length)
{
	int nChild;
	int nTemp;

	for (nTemp = data[i]; 2 * i + 1 < length; i = nChild)
	{
		nChild = 2 * i + 1;
		if (nChild < length - 1 && data[nChild + 1] > data[nChild])
		{
			nChild++;
		}

		if (nTemp < data[nChild])
		{
			data[i] = data[nChild];
			data[nChild] = nTemp;
		}
		else
			break;
	}
}

void HeapSort(int data[], int length)
{
	for (int i = (length >> 1) - 1; i >= 0; i--)
	{
		HeapAjust(data, i, length);
	}

	for (int j = length - 1; j > 0; --j)
	{
		int temp = data[j];
		data[j] = data[0];
		data[0] = temp;
		HeapAjust(data, 0, j);
	}
}

void Merge(int a[], int start, int mid, int end)
{
	int n1 = mid - start + 1;
	int n2 = end - mid;
	int* left = new int[n1];
	int* right = new int[n2];
	int i, j, k;

	for (i = 0; i < n1; i++) /* left holds a[start..mid] */
		left[i] = a[start + i];
	for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
		right[j] = a[mid + 1 + j];

	i = j = 0;
	k = start;
	while (i < n1 && j < n2)
		if (left[i] < right[j])
			a[k++] = left[i++];
		else
			a[k++] = right[j++];

	while (i < n1) /* left[] is not exhausted */
		a[k++] = left[i++];
	while (j < n2) /* right[] is not exhausted */
		a[k++] = right[j++];

	delete[] left;
	delete[] right;
}

void MergeSort(int a[], int start, int end)
{
	int mid;
	if (start < end)
	{
		mid = (start + end) / 2;

		// Divide + Conquer
		MergeSort(a, start, mid);
		MergeSort(a, mid + 1, end);

		// Combine
		Merge(a, start, mid, end);
	}
}

void printArray(int a[], int n)
{
	std::cout << "array elements = [";

	for (int i = 0; i < n; ++i)
	{
		if (i == 0)
		{
			std::cout << a[i];
		}
		else
		{
			std::cout << "," << a[i];
		}
	}

	std::cout << "]" << std::endl;
}

void main()
{
	int a[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	Bublesort(a, sizeof(a) / sizeof(a[0]));
	printArray(a, sizeof(a) / sizeof(a[0]));

	int b[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	QuickSort(b, 0, sizeof(b) / sizeof(b[0]) - 1);
	printArray(b, sizeof(b) / sizeof(b[0]));

	int c[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	InsertSort(c, sizeof(c) / sizeof(c[0]));
	printArray(c, sizeof(c) / sizeof(c[0]));

	int d[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	BInsertSort(d, sizeof(d) / sizeof(d[0]));
	printArray(d, sizeof(d) / sizeof(d[0]));

	int e[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	ShellSort(e, sizeof(e) / sizeof(e[0]));
	printArray(e, sizeof(e) / sizeof(e[0]));

	int f[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	HeapSort(f, sizeof(f) / sizeof(f[0]));
	printArray(f, sizeof(f) / sizeof(f[0]));

	int g[] = { 3, 2, 8, 10, 4, 2, 23, 9 ,1 };
	MergeSort(f, 0, sizeof(g) / sizeof(g[0]) - 1);
	printArray(f, sizeof(g)/ sizeof(g[0]));
}
